package leetcode_day._2021._202104._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/15 8:55
 * 打家劫舍 II
 * 这道题和 198 的区别在于它的房屋是环状的，
 * 可能会出现第一个房屋和最后一个房屋都偷了
 * 方法和 198 的一样，dp[i] = max(dp[i - 1], nums[i] - nums[i - 2])
 * 只是要算两次，分成 0 ~ n-2 和 1 ~ n 两部分
 */
public class _15_213 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 1, 3, 100};
        System.out.println(new _15_213().rob(nums));
    }

    public <T extends Comparable> int c(T a, T b) {
        return a.compareTo(b);
    }

    public int rob(int[] nums) {
//        if (nums.length == 0) return 0;
//        if (nums.length == 1) return nums[0];
        int len = nums.length;
        System.out.println(method(nums, 0, len - 2));
        System.out.println(method(nums, 1, len - 1));
        return Math.max(method(nums, 0, len - 2), method(nums, 1, len - 1));
    }

    // 普通的打家劫舍，dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
    public int method(int[] nums, int begin, int end) {
        int pre1 = 0, pre2 = 0;
        for (int i = begin; i <= end; i++) {
            int tem = pre2;
            pre2 = Math.max(nums[i] + pre1, pre2);
            pre1 = tem;
        }
        return pre2;
    }
}
